package com.breeze.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 * 160. 相交链表
 * 编写一个程序，找到两个单链表相交的起始节点。
 */
public class LeetCode160 {
    /**
     * 方法一：暴力法
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        while (l1 != null) {
            while (l2 != null) {
                if (l1 == l2) {
                    return l2;
                }
                l2 = l2.next;
            }
            l2 = headB;
            l1 = l1.next;
        }
        return null;
    }

    /**
     * 方法二： 哈希表
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * 性能相比方法1提高很多，但依然较差
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode l1 = headA;
        ListNode l2 = headB;
        while (l1 != null) {
            set.add(l1);
            l1 = l1.next;
        }
        while (l2 != null) {
            if (set.contains(l2)) {
                return l2;
            } else {
                l2 = l2.next;
            }
        }
        return null;
    }

    /**
     * 方法三： 最优方法
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * <p>
     * 有两个链表:
     * pA 1->2->3->4->5
     * pB 6->3->4->5
     * 如果分别拼接对方的链表:
     * 1->2->3->4->5->6->3->4->5
     * -
     * 6->3->4->5->1->2->3->4->5
     * -
     * 会发现两个链表长度相同，如果存在相交，则后面的相交处位置相同，这样很容易找到相交节点;如果在拼接链表时，在pA.next为null就指向headB,那么如果两个链表无相交就会导致无线循环。
     * 巧妙点在于pA == null 再指向headB，这样如果没有相交，pA和pB就会在null处相遇。
     * <p>
     * 例如两个链表
     * pA 1->2->3->4
     * pB 5->6->7
     * 1->2->3->4->null->5->6->7->null
     * 5->6->7->null->1->2->3->4->null
     * 无相交，遍历到最后都为null时相遇，也就是无相交。
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    static public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args) {
        ListNode common = new ListNode(5);
        common.next = new ListNode(6);
        common.next.next = new ListNode(7);
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(3);
        headA.next.next = common;
        ListNode headB = new ListNode(2);
        headB.next = common;
        LeetCode160 leetCode160 = new LeetCode160();
        System.out.println(leetCode160.getIntersectionNode(headA, headB).val);
        System.out.println(leetCode160.getIntersectionNode2(headA, headB).val);
        System.out.println(leetCode160.getIntersectionNode3(headA, headB).val);
    }
}
